/*
 * @lc app=leetcode id=241 lang=cpp
 *
 * [241] Different Ways to Add Parentheses
 */
class Solution {
private:
    map<char, std::function<int(int,int)>> method {
        {'-', [](int a, int b) {return a-b;} },
        {'+', [](int a, int b) {return a+b;} },
        {'*', [](int a, int b) {return a*b;} }
    };
public:

    vector<int> diffWaysToCompute(string input) {
        int len = input.size();
        return dowork(input, 0, len-1);
    }

    vector<int> dowork(const string& input, int st, int ed) {
        vector<int> r;
        bool isAllNum = true;
        for (int i=st; i<=ed; i++) {
            char op = input[i];
            if (method.find(op) != method.end()) {
                vector<int> v1 = dowork(input, st, i-1);
                vector<int> v2 = dowork(input, i+1, ed);
                for (auto a : v1) {
                    for (auto b : v2) {
                        r.push_back(method[op](a, b));
                    }
                }
                isAllNum = false;
            }
        }
        if (isAllNum) {
            r.push_back(stoi(input.substr(st, ed-st+1)));
        }
        return r;
    }
};

